package week07

// 44. 通配符匹配
// https://leetcode-cn.com/problems/wildcard-matching/

func isMatch(s string, p string) bool {
	var m, n = len(s), len(p)
	s, p = " " + s, " " + p
	var dp = make([][]bool, m+1)
	for i := range dp {
		dp[i] = make([]bool, n+1)
	}
	dp[0][0] = true
	for j := 1; j <= n && p[j] == '*'; j++ {
		dp[0][j] = true
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if p[j] == '*' {
				dp[i][j] = dp[i-1][j] || dp[i][j-1]
			} else if p[j] == '?' {
				dp[i][j] = dp[i-1][j-1]
			} else {
				dp[i][j] = dp[i-1][j-1] && s[i] == p[j]
			}
		}
	}
	return dp[m][n]
}